package org.example.sword2offer.primary;

import java.util.HashMap;

/**
 * @author: lynn
 * @Descript: LRU 算法
 * @date: 2021/5/6 23:31
 * @version: 1.0
 */
public class Q64_LRU {

    //lru算法内部存放节点 Node
   private class Node{
       public Node pre;
       public Node next;
       public String key;
       public String value;

       Node(String key,String value){
           this.key=key;
           this.value=value;
       }
   }

   private Node head;
   private Node end;
   private int limit; //存储上限
   private HashMap<String,Node> hashMap;


   public Q64_LRU(int limit){
       this.limit=limit;
       hashMap=new HashMap<String,Node>(); //fixme 很容器错
   }

   public String get(String key){
       Node node=hashMap.get(key);
       if (node==null) return null;
       refreshNode(node);
       return node.value;
   }

   public void put(String key,String value){
       Node node=hashMap.get(key);
       if (node==null){
           //如果key不存在，则插入 key-value
           if (hashMap.size()>=limit){
               String oldKey=removeNode(head);
               hashMap.remove(oldKey);
           }
           node=new Node(key,value);
           addNode(node);
           hashMap.put(key,node);
       }else {
           //如果key存在，则刷新key-value
           node.value=value;
           refreshNode(node);
       }
   }


   public void remove(String key){
       Node node=hashMap.get(key);
       removeNode(node);
       hashMap.remove(key);
   }


    /**
     * 刷新节点
     */

    private void refreshNode(Node node){
        if (node==end){
            return;
        }
        //移除节点
        removeNode(node);
        //重新插入节点
        addNode(node);
    }

    /**
     * 删除节点
     */
    private String removeNode(Node node){ //fixme 返回key
        if (node==head && node==end){
            //移除唯一节点
            head=null;
            end=null;
        }else if (node==end){
            //移除尾节点
            end=end.pre;
            end.next=null;
        }else if (node==head){
            //移除头结点
            head=head.next;
            head.pre=null;
        }else {
            //移除中间节点
            node.pre.next=node.next;
            node.next.pre=node.pre;
        }
        return node.key;
    }


    /**
     * 尾部插入节点
     */
    private void addNode(Node node){
        if (end!=null){
            end.next=node;
            node.pre=end;
            node.next=null;//fixme 就会导致满了时候出问题
        }
        end=node; //fixme 容易漏
        if (head==null){ head=node; } //fixme 容易漏
    }


    public static void main(String[] args) {
        Q64_LRU lru=new Q64_LRU(5);
        lru.put("001","用户1信息");
        lru.put("002","用户1信息");
        lru.put("003","用户1信息");
        lru.put("004","用户1信息");
        lru.put("005","用户1信息");
        lru.get("002");
        lru.put("004","用户2信息更新");
        lru.put("006","用户6信息");
        System.out.println(lru.get("001"));
        System.out.println(lru.get("006"));
    }
}
